|
In graph theory, the Cartesian product ''G'' ''H'' of graphs ''G'' and ''H'' is a graph such that * the vertex set of ''G'' ''H'' is the Cartesian product ''V(G)'' × ''V(H)''; and * any two vertices ''(u,u')'' and ''(v,v')'' are adjacent in ''G'' ''H'' if and only if either * * ''u'' = ''v'' and ''u' '' is adjacent with ''v' '' in ''H'', or * * ''u' '' = ''v' '' and ''u'' is adjacent with ''v'' in ''G''. Cartesian product graphs can be recognized efficiently, in linear time.〔. For earlier polynomial time algorithms see and .〕 The operation is commutative as an operation on isomorphism classes of graphs, and more strongly the graphs ''G'' ''H'' and ''H'' ''G'' are naturally isomorphic, but it is not commutative as an operation on labeled graphs. The operation is also associative, as the graphs (''F'' ''G'') ''H'' and ''F'' (''G'' ''H'') are naturally isomorphic. The notation ''G'' × ''H'' is occasionally also used for Cartesian products of graphs, but is more commonly used for another construction known as the tensor product of graphs. The square symbol is the more common and unambiguous notation for the Cartesian product of graphs. It shows visually the four edges resulting from the Cartesian product of two edges. ==Examples== * The Cartesian product of two edges is a cycle on four vertices: K2 K2 = C4. * The Cartesian product of K2 and a path graph is a ladder graph. * The Cartesian product of two path graphs is a grid graph. * The Cartesian product of ''n'' edges is a hypercube: :: :Thus, the Cartesian product of two hypercube graphs is another hypercube: Qi Qj = Qi+j. * The Cartesian product of two median graphs is another median graph. * The graph of vertices and edges of an n-prism is the Cartesian product graph K2 Cn. * The rook's graph is the Cartesian product of two complete graphs. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「cartesian product of graphs」の詳細全文を読む スポンサード リンク
|